#include "main.h"
//функция меняет значения у переменных a и b
void swap(int& a, int&b)
{
     int temp = a;
     a = b;
     b = temp;
}
//Функция сортирует массив a состоящий из size 
//элементов методом сортировки выбором, и возвращает количество сравнений
long long Sort_selection(int* a, int size)
{
     long long NumberSwap = 0;
     for (int i = 0; i < size - 1; i++)
     {
         int mini = i;
         for (int j = i + 1; j < size; j++)
         {
             NumberSwap++;
             if (a[j] < a[mini]) mini = j;
         };
         swap(a[i], a[mini]);
     }
     return NumberSwap;
};
//Функция сортирует массив a состоящий из size 
//элементов методом сортировки вставками, и возвращает количество сравнений
long long Sort_insertion(int *a, int size)
{
	long long NumberSwap = 0;
	for (int i = 1; i < size; i++)
	{
		int temp = a[i];
		for (int j = i-1; j >= 0; j--)
		{
			//если нашли элемент с ключом меньшим, чем текущий элемент, подлежащий вставке, вставляем и выходим из цикла
			NumberSwap++;
			if (a[j] < temp)
			{
				a[j+1] = temp;
				break;
			}else
			//свигаем элемент
			{
				a[j+1] = a[j];
				if (j == 0)a[j] = temp;
			}
		}
	}
	return NumberSwap;
}
//Функция сортирует массив методом обмена
long long Sort_swap(int *a, int size)
{
	long long NumberSwap = 0;
	for (int i = 1; i < size - 1; i++)
	{
		for (int j = size; j >= i; j--)
		{
			NumberSwap++;
			if (!(a[j] > a[j-1]))swap(a[j],a[j-1]);
		}
	}
	return NumberSwap;
}
//Функция сортирует массив методом обмена, улучшение первое
//на каждом проходе смотрим, были ли обмены, если не было, выходим
long long Sort_swap_update1(int *a, int size)
{
	bool error = false;
	long long NumberSwap = 0;
	for (int i = 1; (i < size) && (!error); i++)
	{
		error = true;
		for (int j = size; j >= i; j--)
		{
			NumberSwap++;
			if (!(a[j] > a[j-1]))
			{
				swap(a[j],a[j-1]);
				error = false;
			}
		}
	}
	
	return NumberSwap;
}
//Функция сортирует массив методом обмена, улучшение второе
//на каждом проходе фиксируем последний элемент учавствующий в обмене
long long Sort_swap_update2(int *a, int size)
{
	bool error = false;
	long long NumberSwap = 0;
	//старый минимум, до которого будем подниматься
	int old_min = 1;
	int min;
	int j;
	do{
		error = true;
		j = size - 1;
		while(j >= old_min)
		{
			NumberSwap++;
			if (!(a[j] >= a[j-1]))
			{
				swap(a[j],a[j-1]);
				//запоминаем номер последнего элемента, участвующего в обмене
				min = j;
				error = false;
			}
			j--;
		}
		//меняем старый минимум
		if (!error)old_min = min + 1;
	}while(!error);
	return NumberSwap;
}

//Функция сортирует массив a состоящий из size 
//элементов методом сортировки Шелла
long long Sort_Shell(int *a, int size)
{
	long long NumberSwap = 0;
	//вычислим шаги
	int h0 = 1;
	//количество шагов
	int n = 0;
	while (h0 <= size)
	{
		h0 = h0*3 + 1;
		n++;
	};
	//выделим память под массив, хранящий шаги
	int *h = new int[n];
	h[0] = 1;
	for (int i = 1;  i < n; i++) h[i] = h[i-1]*3 + 1;
	for (int k = n - 1; k >=0; k--)
	{
		for (int i = 0; i < size; i++)
		{
			int temp = a[i];
			for (int j = i - h[k]; j >= 0; j -= h[k])
			{
				NumberSwap++;
				if (a[j] < temp)
				{
					a[j+h[k]] = temp;
					break;
				}else
				//свигаем элемент
				{
					a[j+h[k]] = a[j];
					if ((j - h[k]) < 0)a[j] = temp;
				}					
			}
		
		}
	}
	delete []h;
	return NumberSwap;
}
//Сортировка Хоара, немного мудрёно из-за того что в массиве могут быть одинаковые элементы, и их сортировать не надо
long long QuickSort(int *a, int beg, int end)
{
	if (beg == end)return 0;
	if (end - beg == 1)
	{
		if (!(a[beg]< a[end]))swap(a[beg], a[end]);
		return 1;
	};
	long long NumberSwap = 0;
	int l = beg;
	int r = end;
	int base = a[beg + ((end - beg)/2)];
	do
	{
		while (a[l] < base)l++;
		if (a[l] == base)
		{
			while ((r >= 0) && (a[r] >= base))
			{
				r--;
				NumberSwap++;
			}
		}else
		{
			while ((r >= 0) && (a[r] > base))
			{
				r--;
				NumberSwap++;
			}
		}

		if (r < 0) r++;
		if (r > l) swap(a[l], a[r]);
		if (r == l) break;
		if (r < l)
		{
			while((r <= end) && (a[r] <= base))
			{	 
				r++;
				NumberSwap++;
			}
			if (r == end + 1) r--;
			break;
		};
	}while (r > l);
	if (l == beg) NumberSwap += QuickSort(a, beg, beg);
	else NumberSwap += QuickSort(a, beg, l-1);
	if (r == l) NumberSwap += QuickSort(a, r + 1, end);
	else NumberSwap += QuickSort(a, r, end);
	return NumberSwap;
};
int left(int root)
{ 
	return (root + 1)*2 - 1;
}
int right(int root)
{ 
	return (root + 1)*2 ;
}
//Просеивание вниз
long long MakeHeap(int *a, int _root_, int size)
{
	long long NumberSwap = 0;
	while (_root_ < size && left(_root_) < size && right(_root_) < size)
	{
		NumberSwap++;
		if (left(_root_) < size && right(_root_) < size)
		{
			if (a[left(_root_)] > a[right(_root_)])
			{
				if (a[_root_] < a[left(_root_)])
				{
					swap(a[_root_],a[left(_root_)]);
					_root_ = left(_root_);
				}else break;
			}else
			{
				if (a[_root_] < a[right(_root_)])
				{
					swap(a[_root_],a[right(_root_)]);
					_root_ = right(_root_);
				}else break;
			}
		}else
		{
			if (a[_root_] < a[left(_root_)])
			{
				swap(a[_root_],a[left(_root_)]);
				_root_ = left(_root_);
			}else break;			
		}
	}
	return NumberSwap;
};
long long HeapSort(int *a, int size)
{
	long long NumberSwap = 0;
	//Строим пирамиду
	for (int i = size - 1; i >= 0; i--) MakeHeap(a, i, size);
	while (size > 0)
	{
		size--;
		swap(a[0], a[size]);
		NumberSwap += MakeHeap(a, 0, size);
	};
	return NumberSwap;
}
